#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;


//零钱兑换II(优化版)
//https://leetcode.cn/problems/coin-change-ii/
//class Solution {
//public:
//    int change(int amount, vector<int>& coins) {
//        int n = coins.size();
//        //dp[i][k] 表示在前i个硬币中凑出k数 最大的凑法数
//        //当没有硬币要凑出0时是可以凑出的
//        vector<int> dp(amount + 1);
//        dp[0] = 1;
//
//        //dp[i][k] = dp[i-1][k]+dp[i][k-coins[i-1]];
//        for (int i = 0; i < n; ++i)
//            for (int k = coins[i]; k <= amount; ++k)
//                dp[k] += dp[k - coins[i]];
//
//        return dp[amount];
//    }
//};

//完全平方数(优化版)
//https://leetcode.cn/problems/perfect-squares/submissions/
// class Solution {
// public:
//     int numSquares(int n) {
//         int num = sqrt(n);
    
//         //dp[i][k]表示在前i个数字中选择可以组成k的数 的最小数字选择
//         //当没有数字可选时 无法选择 为0 dp[0][0] = 0 dp[0][1 ~ k] = 0x3f3f3f3f
//         //当需要凑出0时 都不选即可
//         vector<int> dp(n+1);
//         for(int i = 1;i<=n;++i) dp[i] = 0x3f3f3f3f;

//         for(int i = 1;i<=num;++i)
//             for(int k = (i*i);k<=n;++k)
//                 dp[k] = min(dp[k],dp[k-(i*i)]+1);

//         return dp[n];
//     }
// };

//一和零(优化)
//https://leetcode.cn/problems/ones-and-zeroes/
// class Solution {
// public:
//     int findMaxForm(vector<string>& strs, int m, int n) {
//         //dp[i][j][k]表示:在前i个字符串中 找到的0字符不超过j 1字符不超过k的所有选法中 字符串的最大长度

//         // 二维0/1背包问题
//         int len = strs.size();

//         vector<vector<int>> dp(m+1,vector<int>(n+1));

//         for(const auto& str:strs)
//         {
//             int a = 0; //统计该字符串中0个数
//             int b = 0; //统计该字符串中1个数
//             for(const auto& ch:str) 
//             {
//                 if(ch == '0') ++a;
//                 else ++b;
//             }

//             //因为会用到前面的数据 所以需要从后向前遍历
//             for(int j = m;j>=a;--j) //选择0字符个数
//                 for(int k = n;k>=b;--k) //选择1字符个数
//                     dp[j][k] = max(dp[j][k],dp[j-a][k-b]+1); //长度+1
//         }
//         return dp[m][n];
//     }
// };